home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 379_01 / zoo210s.zoo / lzd.c < prev    next >
C/C++ Source or Header  |  1991-07-12  |  31KB  |  848 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. /*********************************************************************/
  6. /* This file contains two versions of the lzd() decompression routine.
  7. The default is to use a fast version coded by Ray Gardner.  If the
  8. symbol SLOW_LZD is defined, the older slower one is used.  I have tested
  9. Ray's code and it seems to be portable and reliable.  But if you
  10. suspect any problems you can define SLOW_LZD for your system in
  11. options.h and cause the older code to be used.  --R.D. */
  12. /*********************************************************************/
  13.  
  14. #include "options.h"
  15. #include "zoo.h"
  16. #include "zooio.h"
  17. #include "various.h"
  18. #include "zoofns.h"           /* function definitions */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. #include "lzconst.h"
  23.  
  24. #ifndef SLOW_LZD
  25.  
  26. /* Extensive modifications for speed by Ray Gardner
  27. ** Public domain by Raymond D. Gardner  9/26/88
  28. **
  29. ** I apologize for the comments being so dense in places as to impair
  30. ** readability, but some of the stuff isn't very obvious and needs
  31. ** some explaining.  I am also sorry for the messy control structure
  32. ** (quite a few labels and goto's) and very long lzd() function, but
  33. ** I don't know how to do this any other way without loss of speed.
  34. **
  35. ** Ray Gardner
  36. ** 6374 S. Monaco Ct.
  37. ** Englewood, CO 80111
  38. */
  39.  
  40. #ifdef ANSI_HDRS
  41. # include <string.h>        /* to get memcpy */
  42. #else
  43.   VOIDPTR memcpy();
  44. #endif
  45.  
  46. #define  STACKSIZE   4000  /* allows for about 8Mb string in worst case? */
  47. /* stack grows backwards in this version, using pointers, not counters */
  48. static char *stack;
  49. static char *stack_pointer;
  50. static char *stack_lim;
  51.  
  52. void init_dtab PARMS((void));
  53. unsigned rd_dcode PARMS((void));
  54. /* void wr_dchar (char); */        /* now a macro */
  55. void ad_dcode PARMS((void));
  56.  
  57. #ifdef FILTER
  58. /* to send data back to zoofilt */
  59. extern unsigned int filt_lzd_word;
  60. #endif /* FILTER */
  61.  
  62. void xwr_dchar PARMS ((char));
  63. static int firstchar PARMS ((int));
  64. static void cbfill PARMS ((void));
  65.  
  66. /* wr_dchar() is a macro for speed */
  67. #define wr_dchar(c) {                             \
  68.                            if (outbufp<outbuflim) \
  69.                               *outbufp++=(c);     \
  70.                            else                   \
  71.                               xwr_dchar(c);       \
  72.                     }
  73.  
  74. extern char *out_buf_adr;        /* output buffer */
  75. extern char *in_buf_adr;         /* input buffer */
  76.                       /* use pointers (not counters) for buffer (for speed) */
  77. static char *outbufp;            /* output buffer pointer */
  78. static char *outbuflim;          /* output buffer limit */
  79. static char *outbufguard;        /* output buffer "guard" */
  80.  
  81. char memflag = 0;                /* memory allocated? flag */
  82. int *head;                       /* lzw prefix codes */
  83. char *tail;                      /* lzw suffix codes */
  84. static unsigned cur_code;
  85. static unsigned old_code;
  86. static unsigned in_code;
  87.  
  88. static unsigned free_code;
  89. static int nbits;
  90. static unsigned max_code;
  91.  
  92. /* We use a buffer of codes to avoid a function call to unpack each
  93. ** one as needed.  We allocate an extra slot past the end of the buffer
  94. ** and put a CLEAR code in it, to serve as a sentinel.  This way we can
  95. ** fold the test for code buffer runout into the test for a clear code
  96. ** and avoid having an extra test on each code processed.  Also, we don't
  97. ** always use the code buffer.  We can only use it when the input buffer
  98. ** is at a byte boundary, and when we know that the codesize won't change
  99. ** before we fill the code buffer, and when we know we won't run out of
  100. ** bytes in the input buffer before filling the code buffer.  So we start
  101. ** with the code buffer pointer pointing to the sentinel, and we always
  102. ** have it pointing at the sentinel when we can't (for one reason or
  103. ** another) be getting our codes from the code buffer.  We check for this
  104. ** condition whenever we get a CLEAR code, and if so, we get the code
  105. ** via the good old rd_dcode() routine.
  106. **
  107. ** One other problem with the code buffer approach is that we might get
  108. ** a CLEAR code in the middle of the buffer.  This means that the next
  109. ** code is only 9 bits, but we have probably already unpacked a number of
  110. ** larger codes from the input into the buffer before we discover this.
  111. ** So we remember where (in the input buffer) the code buffer was filled
  112. ** from, and when a CLEAR code is encountered in the buffer (not the
  113. ** sentinel at the end) we back up the bit_offset pointer in the input
  114. ** buffer, and reset things to start unpacking the 9-bit codes from there.
  115. */
  116.  
  117. #define CODEBUF_SIZE 64      /* must be multiple of 8, experiment for best */
  118. static unsigned codebuf[CODEBUF_SIZE+1];     /* code buffer */
  119. static unsigned *codebufp;       /* code buffer pointer */
  120. static unsigned *codebuflim;     /* code buffer limit */
  121.       /* bit offset within the input buffer of where the code buffer began */
  122. static unsigned codebufoffset;
  123.  
  124. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  125.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  126. static unsigned bit_offset;   /* note this only allows max 8K input buffer!!*/
  127.  
  128. #ifdef UNBUF_IO
  129. #define        BLOCKFILE        int
  130. #define        BLOCKREAD        read
  131. #define        BLOCKWRITE        blockwrite
  132. int read PARMS ((int, VOIDPTR, unsigned));
  133. int write PARMS ((int, VOIDPTR, unsigned));
  134. int blockwrite PARMS ((int, VOIDPTR, unsigned));
  135. #else
  136. #define        BLOCKFILE        ZOOFILE
  137. #define        BLOCKREAD        zooread
  138. #define        BLOCKWRITE        zoowrite
  139. #endif /* UNBUF_IO */
  140.  
  141. static BLOCKFILE in_f, out_f;
  142.  
  143. /* rd_dcode() reads a code from the input (compressed) file and returns
  144. its value. */
  145. unsigned rd_dcode()
  146. {
  147.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  148.    unsigned word;                     /* first 16 bits in buffer */
  149.    unsigned byte_offset;
  150.    char nextch;                           /* next 8 bits in buffer */
  151.    unsigned ofs_inbyte;               /* offset within byte */
  152.  
  153.    ofs_inbyte = bit_offset % 8;
  154.    byte_offset = bit_offset / 8;
  155.    bit_offset = bit_offset + nbits;
  156.  
  157.    assert(nbits >= 9 && nbits <= 13);
  158.  
  159.    if (byte_offset >= INBUFSIZ - 5) {
  160.       int space_left;
  161.  
  162.       assert(byte_offset >= INBUFSIZ - 5);
  163.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  164.  
  165.       bit_offset = ofs_inbyte + nbits;
  166.       space_left = INBUFSIZ - byte_offset;
  167.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  168.       ptra = in_buf_adr;
  169.       /* we now move the remaining characters down buffer beginning */
  170.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  171.       while (space_left > 0) {
  172.          *ptra++ = *ptrb++;
  173.          space_left--;
  174.       }
  175.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  176.       assert(space_left == 0);
  177.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  178.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  179.       byte_offset = 0;
  180.    }
  181.    ptra = byte_offset + in_buf_adr;
  182.  /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  183.    word = (unsigned char) *ptra; ptra++;
  184.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  185.  
  186.    nextch = *ptra;
  187.    if (ofs_inbyte != 0) {
  188.       /* shift nextch right by ofs_inbyte bits */
  189.       /* and shift those bits right into word; */
  190.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  191.    }
  192.    return (word & masks[nbits]); 
  193. } /* rd_dcode() */
  194.  
  195. void init_dtab()
  196. {
  197.    nbits = 9;
  198.    max_code = 512;
  199.    free_code = FIRST_FREE;
  200. }
  201.  
  202. /* By making wr_dchar() a macro and calling this routine only on buffer
  203. ** full condition, we save a lot of function call overhead.
  204. ** We also use pointers instead of counters for efficiency (in the macro).
  205. */
  206. void xwr_dchar (ch)
  207. char ch;
  208. {
  209.    if (outbufp >= outbuflim) {      /* if buffer full */
  210.       if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  211.                                                 != outbufp - out_buf_adr)
  212.          prterror ('f', "Write error in lzd:wr_dchar.\n");
  213.